package gold.digger;

import gold.utils.InputUtil;

import java.util.Arrays;
import java.util.Comparator;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC354 {
    public int maxEnvelopes(int[][] envelopes) {
        // 按宽度升序排列，如果宽度一样，则按高度降序排列
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] == b[0] ?
                        b[1] - a[1] : a[0] - b[0];
            }
        });

        int[] dp = new int[envelopes.length];
        // base case：dp 数组全都初始化为 1
        Arrays.fill(dp, 1);
        for (int i = 0; i < envelopes.length; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;

    }


    public static void main(String[] args) {
        LC354 an = new LC354();
        int[][] envelops = InputUtil.toDoubleIntegerArray("[[5,4],[6,4],[6,7],[2,3]]");
        System.out.println(an.maxEnvelopes(envelops));
    }
}
